package L610;

import util.ListNode;

/**
 * @program: javase
 * @description: 合并两个有序链表
 * @author: luolidong
 * @create: 2021-06-11 21:16
 * @version: 1.0
 */
public class Demo3 {
//    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//        // time n+m;space 1
//        ListNode dummy = new ListNode(0);
//        // 不用cur=dummy.next;
//        ListNode cur = dummy;
//        while (l1 != null && l2 != null) {
//            if (l1.val > l2.val) {
//                cur.next = l2;
//                l2 = l2.next;
//            } else {
//                cur.next = l1;
//                l1 = l1.next;
//            }
//            cur = cur.next;
//        }
//        cur.next = l1 == null ? l2 : l1;
//        return dummy.next;
//    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // time n+m;space n+m
        if(l1==null||l2==null) return l1==null?l2:l1;
        if(l1.val<l2.val){
            l1.next=mergeTwoLists(l1.next, l2);
            return l1;
        }else {
            l2.next=mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
